package dfs;

import java.util.*;

/**
 * @author wcj
 * @Date 2021/7/6 18:37
 * @Version 1.0
 */
public class PhoneCompose {

    private static List<String> res;
    private static StringBuffer sb;
    private static String str;
    private static Map<Character, String[]> map;

    /**
     * 电话号码的字母组合：根据电话号码和字母的映射关系，输出给出的只包含2-9的数字的所有字母组合
     * 2-abc
     * 3-def
     * 4-ghi
     * 5-jkl
     * 6-mno
     * 7-pqrs
     * 8-tuv
     * 9-wxyz
     * 深搜：
     * ①递归方法的设计：dfs(int index)其中index为当前访问到的字符索引
     * ②递归出口：index == s.length()截止
     * ③递归组合方式：每个数字有自己对应的字母
     *
     * @param s
     * @return
     */
    public static List<String> phoneCompose(String s) {
        map = new HashMap<>();
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
        res = new ArrayList<>();
        sb = new StringBuffer();
        str = s;
        dfs(0);
        return res;
    }

    public static void dfs(int index) {
        // 递归截止条件
        if (index == str.length()) {
            res.add(sb.toString());
            return;
        }
        // 递归组合方式
        String[] tmp = map.get(str.charAt(index));
        for (int i = 0; i < tmp.length; i++) {
            sb.append(tmp[i]);
            dfs(index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
